PAT--乙 1013 数素数

1013 数素数(题解)

令 Pi表示第 i 个素数。现任给两个正整数 M≤N≤10exp4，请输出 PM到 P N的所有素数。

输入格式:

输入在一行中给出 M 和 N，其间以空格分隔。

输出格式:

输出从 PM到 P N的所有素数，每 10 个数字占 1 行，其间以空格分隔，但行末不得有多余空格。

样例输入:

5 27

样例输出：

1
2
3

11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103

代码如下:

#include <stdio.h>
bool prime[1000001]={0};
int p[1000001];
void find(int n)
{
	int count=0;
	for(int i=2;;i++)
	{
		if(prime[i]==false)
		{
			p[count++]=i;
			for(int j=2*i;j<1000001;j=j+i)
				prime[j]=true;
		}
		if(count>=n)
			break;
	}
}
int main()
{
	int m,n,c=0;
	scanf("%d%d",&m,&n);
	find(n);
	for(int i=m;i<=n;i++)
	{
		printf("%d",p[i-1]);
		c++;
		if(c%10==0||i==n)
			printf("\n");
		else
			printf(" ");
	}	
	return 0;
}